/*
 *时间复杂度 O(n^2)
 *空间复杂度 O(1)
 
 算法描述
  （1）从第一个元素开始，该元素可以认为已经被排序；
  （2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
  （3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
  （4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 （5）将新元素插入到该位置后；
  （6）重复步骤（2）~（5）。
 */
console.log('---------------------优化前的插入算法-----------------------------');

function worstInsertionSort(nums) {
	var len = nums.length;
	var preIndex, current;
	for (var i = 1; i < len; i++) {
		preIndex = i - 1;
		current = nums[i];
		while (preIndex >= 0 && nums[preIndex] > current) {
			nums[preIndex + 1] = nums[preIndex];
			preIndex--;
		}
		nums[preIndex + 1] = current;
		console.log(`第${i}趟`, nums);
	}
	return nums;
}
const nums = [3, 4, 5, 7, 3, 5, 8]
worstInsertionSort(nums)